package srm513;

import java.util.Arrays;

public class YetAnotherIncredibleMachine {
    private static final int MOD = 1000000009;

    public int countWays(int[] platformMount, int[] platformLength, int[] balls) {
        Arrays.sort(balls);
        int[] diffWays = new int[platformLength.length];
        int x, y;
        int bLen = balls.length;

        for (int i = 0; i < diffWays.length; i++) {
            x = platformMount[i];
            y = i + 1;
            int left = x - platformLength[i], right = x + platformLength[i], l, r;
            l = Arrays.binarySearch(balls, left);
            if (l < 0) {
                l = -l - 1;
            }
            r = Arrays.binarySearch(balls, right);
            if (r < 0) {
                r = -r - 1;
            }
            int ways = 0;
            boolean valid;
            for (; left <= x; left++) {
                valid = true;
                for (int j = l; j <= r && j >= 0 && j < bLen; j++) {
                    if (balls[j] >= left && balls[j] <= left + platformLength[i]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) ways++;
            }
            diffWays[i] = ways;
        }

        long num = 1;
        for (int i = 0; i < diffWays.length; i++) {
            num *= diffWays[i];
            num = num % MOD;
        }
        return (int) num;
    }

    // BEGIN KAWIGIEDIT TESTING
    // Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
    private static boolean KawigiEdit_RunTest(int testNum, int[] p0, int[] p1, int[] p2, boolean hasAnswer, int p3) {
        System.out.print("Test " + testNum + ": [" + "{");
        for (int i = 0; p0.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p0[i]);
        }
        System.out.print("}" + "," + "{");
        for (int i = 0; p1.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p1[i]);
        }
        System.out.print("}" + "," + "{");
        for (int i = 0; p2.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p2[i]);
        }
        System.out.print("}");
        System.out.println("]");
        YetAnotherIncredibleMachine obj;
        int answer;
        obj = new YetAnotherIncredibleMachine();
        long startTime = System.currentTimeMillis();
        answer = obj.countWays(p0, p1, p2);
        long endTime = System.currentTimeMillis();
        boolean res;
        res = true;
        System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
        if (hasAnswer) {
            System.out.println("Desired answer:");
            System.out.println("\t" + p3);
        }
        System.out.println("Your answer:");
        System.out.println("\t" + answer);
        if (hasAnswer) {
            res = answer == p3;
        }
        if (!res) {
            System.out.println("DOESN'T MATCH!!!!");
        } else if ((endTime - startTime) / 1000.0 >= 2) {
            System.out.println("FAIL the timeout");
            res = false;
        } else if (hasAnswer) {
            System.out.println("Match :-)");
        } else {
            System.out.println("OK, but is it right?");
        }
        System.out.println("");
        return res;
    }

    public static void main(String[] args) {
        boolean all_right;
        all_right = true;

        int[] p0;
        int[] p1;
        int[] p2;
        int p3;

        // ----- test 0 -----
        p0 = new int[]{7};
        p1 = new int[]{10};
        p2 = new int[]{3, 4};
        p3 = 3;
        all_right = KawigiEdit_RunTest(0, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 1 -----
        p0 = new int[]{1, 4};
        p1 = new int[]{3, 3};
        p2 = new int[]{2, 7};
        p3 = 1;
        all_right = KawigiEdit_RunTest(1, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 2 -----
        p0 = new int[]{4, 4, 4};
        p1 = new int[]{10, 9, 8};
        p2 = new int[]{1, 100};
        p3 = 27;
        all_right = KawigiEdit_RunTest(2, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 3 -----
        p0 = new int[]{0};
        p1 = new int[]{1};
        p2 = new int[]{0};
        p3 = 0;
        all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 4 -----
        p0 = new int[]{100, -4215, 251};
        p1 = new int[]{400, 10000, 2121};
        p2 = new int[]{5000, 2270, 8512, 6122};
        p3 = 250379170;
        all_right = KawigiEdit_RunTest(4, p0, p1, p2, true, p3) && all_right;
        // ------------------

        if (all_right) {
            System.out.println("You're a stud (at least on the example cases)!");
        } else {
            System.out.println("Some of the test cases had errors.");
        }
    }
    // END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!
